package leetcode_周赛._2023._05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第 345 场周赛
 * <p>AC_3</p>
 *
 * @author yezh
 * @date 2023/5/16 8:49
 */
public class _14 {

    /**
     * 相邻值的按位异或
     * 算法：位运算
     * derived[0] = original[0] ^ original[1]
     * derived[1] = original[1] ^ original[2]
     * derived[2] = original[2] ^ original[0]
     * derived[0] ^ derived[1] ^ derived[2] = original[0] ^ original[1]
     * ^ original[1] ^ original[2] ^ original[2] ^ original[0] = 0
     */
    public boolean doesValidArrayExist(int[] derived) {
        int res = 0;
        for (int e : derived) res ^= e;
        return res == 0;
    }

    /**
     * 矩阵中移动的最大次数
     * 算法：记忆化搜索(递归)、递推(将记忆化搜索翻译成递推)、BFS
     */
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        int[][] f = new int[m][n];
//        for (int i = 0; i < m; i++) dfs(i, 0, f, grid); // 递归

        // 从后往前走, 跟从前往后比, 不需要判断是否可以继续走下去
        for (int j = n - 2; j >= 0; j--) { // 递推
            for (int i = 0; i < m; i++) {
                // 减少边界判断代码
                for (int k = Math.max(i - 1, 0); k <= Math.min(i + 1, m - 1); k++)
                    if (grid[i][j] < grid[k][j + 1]) f[i][j] = Math.max(f[i][j], f[k][j + 1] + 1);
            }
        }
        for (int i = 0; i < m; i++) ans = Math.max(ans, f[i][0]);
        return ans;
    }

    void dfs(int i, int j, int[][] f, int[][] grid) {
        // 确保每个格子只算一次
        if (f[i][j] != 0) return;
        if (j == grid[0].length - 1) return;
        int res = 0;
        for (int k = Math.max(i - 1, 0); k <= Math.min(i + 1, grid.length - 1); ++k)
            if (grid[i][j] < grid[k][j + 1]) {
                dfs(k, j + 1, f, grid);
                // +1 表示移动一次
                f[i][j] = Math.max(f[i][j], f[k][j + 1] + 1);
            }
    }

    public int maxMoves_bfs(int[][] grid) {
        // 向右搜索
        int m = grid.length, n = grid[0].length;
        List<Integer> q = new ArrayList<>(m);
        // 防止重复访问
        int[] vis = new int[m];
        Arrays.fill(vis, -1);
        for (int i = 0; i < m; i++) q.add(i);
        for (int j = 0; j < n - 1; j++) {
            List<Integer> tmp = q;
            q = new ArrayList<>(m);
            for (int i : tmp) {
                for (int k = Math.max(i - 1, 0); k <= Math.min(i + 1, m - 1); k++)
                    if (vis[k] != j && grid[i][j] < grid[k][j + 1]) {
                        q.add(k);
                        vis[k] = j;
                    }
            }
            // 表示走不下去了
            if (q.isEmpty()) return j;
        }
        return n - 1;
    }

    /**
     * 2685. 统计完全连通分量的数量
     * 算法：DFS
     */
    List<Integer>[] g;
    boolean[] vis;
    int v, e;
    public int countCompleteComponents(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        // 建图
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            g[x].add(y);
            g[y].add(x);
        }
        vis = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                v = 0;
                e = 0;
                dfs(i);
                if (e == v * (v - 1)) ++ans;
            }
        }
        return ans;
    }

    void dfs(int x) {
        vis[x] = true;
        ++v;
        e += g[x].size();
        for (int y : g[x]) if (!vis[y]) dfs(y);
    }

}
